#leetcode题目17：电话号码的字母组合
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：回溯
#目前暂时还没有吃透

# 更好的解法：回溯
# from typing import List
# class Solution:
#     def letterCombinations(self, digits: str) -> List[str]:
#         if not digits and len(digits)==0:
#             return []
#         digit_map={
#             0:"0",
#             1:"1",
#             2:"abc",
#             3:"def",
#             4:"ghi",
#             5:"jkl",
#             6:"mno",
#             7:"pqrs",
#             8:"tuv",
#             9:"wxyz"
#         }
#         res=[]
#         self.backtrack(digits,0,"",res,digit_map)
#         return res
#     def backtrack(self,digits,index,path,res,digit_map):
#         if index==len(digits):
#             res.append(path)
#             return
#         for letter in digit_map[int(digits[index])]:
#             self.backtrack(digits,index+1,path+letter,res,digit_map)


#解法2：视频解法,目前来看为纯粹的迭代法。并且没有用到回溯的思想。
from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits and len(digits)==0:
            return []
        digit_map={
            0:"0",
            1:"1",
            2:"abc",
            3:"def",
            4:"ghi",
            5:"jkl",
            6:"mno",
            7:"pqrs",
            8:"tuv",
            9:"wxyz"
        }
        res=[""]

        for digit in digits:
            temp_list=[]
            #ch是当前字母
            for ch in digit_map[int(digit)]:
                for str_temp in res:#s
                    temp_list.append(str_temp+ch)
            res=temp_list
        return res




#测试数据
digits="23" 
#预期输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
solution=Solution()
print(solution.letterCombinations(digits))

